Search results for "ECO method"

showing 2 items of 2 documents

Enumeration of L-convex polyominoes by rows and columns

2005

In this paper, we consider the class of L-convex polyominoes, i.e. the convex polyominoes in which any two cells can be connected by a path of cells in the polyomino that switches direction between the vertical and the horizontal at most once.Using the ECO method, we prove that the number fn of L-convex polyominoes with perimeter 2(n + 2) satisfies the rational recurrence relation fn = 4fn-1 - 2fn-2, with f0 = 1, f1 = 2, f2 = 7. Moreover, we give a combinatorial interpretation of this statement. In the last section, we present some open problems.

Discrete mathematicsRecurrence relationECO methodGeneral Computer SciencePolyominoGenerating functionRegular polygonRow and column spacesTheoretical Computer ScienceInterpretation (model theory)Generating functionsCombinatoricsSection (fiber bundle)Path (graph theory)Convex polyominoesComputer Science(all)MathematicsTheoretical Computer Science
researchProduct

ECO-generation for some restricted classes of compositions

2013

International audience; We study several restricted classes of compositions by giving one-to-one maps between them and different classes of restricted binary strings or pattern avoiding permutations. Inspired by the ECO method, new succession rules for these classes are presented. Finally, we obtain generating algorithms in Constant Amortized Time (CAT) for theses classes.

[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]succession ruleComposition of an integerECO method[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]lcsh:Electronic computers. Computer science[ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO]generating treepattern avoiding permutationlcsh:QA75.5-76.95
researchProduct